# 给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。
# 有效的运算符号包含 +, - 以及 *。
#
#  示例 1:
#  输入: "2-1-1"
# 输出: [0, 2]
# 解释:
# ((2-1)-1) = 0
# (2-(1-1)) = 2
#
#  示例 2:
#  输入: "2*3-4*5"
# 输出: [-34, -14, -10, -10, 10]
# 解释:
# (2*(3-(4*5))) = -34
# ((2*3)-(4*5)) = -14
# ((2*(3-4))*5) = -10
# (2*((3-4)*5)) = -10
# (((2*3)-4)*5) = 10
from typing import List


class Solution:
    def __init__(self):
        self.dict = {}

    def diffWaysToCompute2(self, expression: str) -> List[int]:
        """
        解法二:分治优化
        使用map将计算过的表达式的结果保存起来后面如果有用到直接取即可
        :param expression:
        :return:
        """
        if expression.isdigit():  # 如果只有数字，转为数字后直接返回
            return [int(expression)]
        res = []
        if expression in self.dict:  # 首先看map中是否存在当前表达式的结果，如果有直接返回，没有再进行计算
            return self.dict[expression]
        for i, curChar in enumerate(expression):
            if curChar in ['+', '-', '*']:  # 分解：遇到运算符，分别计算左右两侧的结果集
                leftList = self.diffWaysToCompute1(expression[:i])  # 计算左侧的结果集
                rightList = self.diffWaysToCompute1(expression[i + 1:])  # 计算右侧的结果集
                for leftNum in leftList:  # 合并：根据运算符合并子问题的解
                    for rightNum in rightList:
                        if curChar == '+':
                            res.append(leftNum + rightNum)
                        elif curChar == '-':
                            res.append(leftNum - rightNum)
                        else:
                            res.append(leftNum * rightNum)
        self.dict[expression] = res  # 将当前表达式的计算结果保存到map中
        return res

    def diffWaysToCompute1(self, expression: str) -> List[int]:
        """
         解法一：分治
         当前表达式中的每个运算符作为左右区间的划分标志,递归进行拆分
         以 2*3-4*5 为例
         差分如下:
          以第一个 '*' 拆分成左右两个子表达式 left = 2 right = 3-4*5 依次递归进行拆分直到表达式可以算出结果为止
             left已经是一个数字，就不再进行拆分， right拆分如下
              以 '-' 拆成 left = 3 right = 4*5
                left不再进行拆分，right以'*'拆分如下
                  left = 4 right = 5
              以 '*' 拆成 left = 3-4 right = 5
                right不再进行拆分，left以'-'拆分为
                 left = 3 right = 4
          以 '-' 拆分成左右两个子表达式 left = 2 * 3 right = 4*5 ....
        :param expression:
        :return:
        """
        if expression.isdigit():  # 如果只有数字，转为数字后直接返回
            return [int(expression)]
        res = []
        for i, curChar in enumerate(expression):
            if curChar in ['+', '-', '*']:  # 分解：遇到运算符，分别计算左右两侧的结果集
                leftList = self.diffWaysToCompute1(expression[:i])  # 计算左侧的结果集
                rightList = self.diffWaysToCompute1(expression[i + 1:])  # 计算右侧的结果集
                for leftNum in leftList:  # 合并：根据运算符合并子问题的解
                    for rightNum in rightList:
                        if curChar == '+':
                            res.append(leftNum + rightNum)
                        elif curChar == '-':
                            res.append(leftNum - rightNum)
                        else:
                            res.append(leftNum * rightNum)
        return res

    def diffWaysToCompute(self, expression: str) -> List[int]:
        return self.diffWaysToCompute2(expression)


if __name__ == "__main__":
    expression = "2*3-4*5"
    print(Solution().diffWaysToCompute(expression))
